package leet;

import java.util.Arrays;

/**
 * 945. Minimum Increment to Make Array Unique
 * 
 * <pre>
 * Given an array of integers A, a move consists of choosing any A[i], and
 * incrementing it by 1.
 * 
 * Return the least number of moves to make every value in A unique.
 * </pre>
 * 
 * @author zhujunbing
 * @date 2019年4月26日
 */
public class Leet0945 {

	public static void main(String[] args) {

		int[] A = { 1, 2, 1, 2, 3, 7 };
		Leet0945 leet0945 = new Leet0945();
		int minIncrementForUnique = leet0945.minIncrementForUnique(A);
		System.out.println(minIncrementForUnique);
	}

	/**
	 * 偷懒的先排序有点慢
	 * @param A
	 * @return
	 * @date 2019年4月26日
	 */
	private int minIncrementForUnique(int[] A) {
		// TODO Auto-generated method stub
		return 0;
	}

	/**
	 * 18ms
	 * 
	 * @param A
	 * @return
	 * @date 2019年4月26日
	 */
	public int minIncrementForUnique0(int[] A) {
		if (A.length == 0) {
			return 0;
		}

		Arrays.sort(A);

		int num = 0;

		for (int i = 1; i < A.length; i++) {
			if (A[i] <= A[i - 1]) {
				num += A[i - 1] - A[i] + 1;
				A[i] = A[i - 1] + 1;
			}
		}

		return num;
	}
}
